翻訳と辞書 Words near each other ・ Metro 21 ・ Metro 3 ・ Metric (band) ・ Metric (mathematics) ・ Metric (unit) ・ Metric (vector bundle) ・ Metric Act of 1866 ・ Metric Arts ・ Metric Commission ・ Metric connection ・ Metric conversion ・ Metric Conversion Act ・ Metric derivative ・ Metric differential ・ Metric dimension ・ Metric dimension (graph theory) ・ Metric discography ・ Metric engine (American expression) ・ Metric expansion of space ・ Metric foot ・ Metric gauge ・ Metric Hosiery Company ・ Metric k-center ・ Metric map ・ Metric Martyrs ・ Metric mile ・ Metric modulation ・ Metric outer measure ・ Metric Pixel Canvas ・ Metric prefix Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Metric dimension (graph theory) ： ウィキペディア英語版 Metric dimension (graph theory) In graph theory, the metric dimension of a graph ''G'' is the minimum number of vertices in a subset ''S'' of ''G'' such that all other vertices are uniquely determined by their distances to the vertices in ''S''. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete. == Detailed definition == For an ordered subset $W\; =\; \backslash$ of vertices and a vertex ''v'' in a connected graph ''G'', the representation of ''v'' with respect to ''W'' is the ordered ''k''-tuple $r(v|W)\; =\; (d(v,w\_1),\; d(v,w\_2),\backslash dots,d(v,w\_k))$, where ''d''(''x'',''y'') represents the distance between the vertices ''x'' and ''y''. The set ''W'' is a resolving set (or locating set) for ''G'' if every two vertices of ''G'' have distinct representations. The metric dimension of ''G'' is the minimum cardinality of a resolving set for ''G''. A resolving set containing a minimum number of vertices is called a basis (or reference set) for ''G''. Resolving sets were introduced independently by and . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Metric dimension (graph theory)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.